package LeetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}21:53
 */
public class LeetCode438 {
    //找到字符串中所有字母异位词
    //给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
    //
    //字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
    //
    //使用滑动窗口来进行 该方法有局限性 只适用p中没有重复字符

    public static void main(String[] args) {
//        System.out.println(new LeetCode438().findAnagrams("abab", "ab").toString());;
        System.out.println(Solution.findAnagrams("abab", "ab").toString());
    }

    public List<Integer> findAnagrams(String s, String p) {
        int[] freq = new int[256];
        //先将p字符串记录进频率数组
        for (char c : p.toCharArray()) {
            freq[c]++;
        }

        //进行窗口滑动
        int l = 0;
        int r = 0;
        char[] chars = s.toCharArray();
        int index = 0;//计数器

        List<Integer> list = new ArrayList<>();
        while (r + 1 < chars.length) {
            index++;
            if (freq[chars[l]] == freq[chars[++r]] && chars[l] != chars[r]) {
                    if (index == p.length() - 1) {
                        list.add(l);
                        l = r;
                        r++;
                        index = 0;
                    }
            }else if (index == p.length() - 1){
                l++;
                r = l;
                index = 0;
            }
        }
        return list;
    }



    static class Solution {
        public static List<Integer> findAnagrams(String s, String p) {
            char[] arrS = s.toCharArray();
            char[] arrP = p.toCharArray();

            // 接收最后返回的结果
            List<Integer> ans = new ArrayList<>();

            // 定义一个 needs 数组来看 arrP 中包含元素的个数
            int[] needs = new int[26];
            // 定义一个 window 数组来看滑动窗口中是否有 arrP 中的元素，并记录出现的个数
            int[] window = new int[26];

            // 先将 arrP 中的元素保存到 needs 数组中
            for (int i = 0; i < arrP.length; i++) {
                needs[arrP[i] - 'a'] += 1;
            }

            // 定义滑动窗口的两端
            int left = 0;
            int right = 0;

            // 右窗口开始不断向右移动
            while (right < arrS.length) {
                int curR = arrS[right] - 'a';
                right++;
                // 将右窗口当前访问到的元素 curR 个数加 1
                window[curR] += 1;

                // 当 window 数组中 curR 比 needs 数组中对应元素的个数要多的时候就该移动左窗口指针
                while (window[curR] > needs[curR]) {
                    int curL = arrS[left] - 'a';
                    left++;
                    // 将左窗口当前访问到的元素 curL 个数减 1
                    window[curL] -= 1;
                }

                // 这里将所有符合要求的左窗口索引放入到了接收结果的 List 中
                if (right - left == arrP.length) {
                    ans.add(left);
                }
            }
            return ans;
        }
    }
}
